package bak;

import java.util.Random;

public class SortingAlgorithm4Long
{
	public void insertionSort(long[] array)
	{
		long item;
		int i, j;
		for (i = 1; i < array.length; i++)
		{
			item = array[i];
			j = i - 1;
			while (j >= 0)
			{
				if (array[j] > item)
				{
					array[j + 1] = array[j];
					j--;
				}
				else
				{
					break;
				}
			}
			array[j + 1] = item;
		}
	}

	public void quickSort(long[] array, int start, int end)
	{
		if (start < end)
		{
			int p = partition(array, start, end);
			quickSort(array, start, p - 1);
			quickSort(array, p + 1, end);
		}
	}

	private int partition(long[] array, int start, int end)
	{
		long tmp, cmp = array[end];
		int i = start - 1, j = start;

		while (j < end)
		{
			if (array[j] < cmp)
			{
				tmp = array[j];
				array[j] = array[i + 1];
				array[i + 1] = tmp;
				i++;
			}
			j++;
		}
		tmp = array[end];
		array[end] = array[i + 1];
		array[i + 1] = tmp;

		return i + 1;
	}

	public void mergeSort(long[] array, int start, int end)
	{
		if (start < end)
		{
			int mid = (start + end) >>> 1;

			mergeSort(array, start, mid);
			mergeSort(array, mid + 1, end);

			// copy sub-array
			long[] leftArr = new long[mid - start + 1];
			for (int i = 0; i < leftArr.length; i++)
			{
				leftArr[i] = array[i + start];
			}

			long[] rightArr = new long[end - mid];
			for (int i = 0; i < rightArr.length; i++)
			{
				rightArr[i] = array[i + mid + 1];
			}

			// merge
			int i = 0, j = 0, index = start;
			while ((i < leftArr.length) && (j < rightArr.length))
			{
				if (leftArr[i] <= rightArr[j])
				{
					array[index++] = leftArr[i++];
				}
				else
				{
					array[index++] = rightArr[j++];
				}
			}
			if (i == leftArr.length)
			{
				while (j < rightArr.length)
				{
					array[index++] = rightArr[j++];
				}
			}
			else
			{
				while (i < leftArr.length)
				{
					array[index++] = leftArr[i++];
				}
			}
		}
	}

	public long[] radixSort(long[] array, int bitRange)
	{
		// because MAX_VALUE of int is 2^31-1, so bitRange must <= 31

		int startBit = 0, endBit = 0;
		while ((endBit = startBit + bitRange - 1) < 32)
		{
			array = countingSort(array, startBit, endBit);
			startBit = endBit + 1;
		}
		if (startBit < 32)
		{
			array = countingSort(array, startBit, 31);
		}
		return array;
	}

	private long[] countingSort(long[] array, int startBit, int endBit)
	{
		// bit index begin with 0
		long[] result = new long[array.length];

		// because MAX_VALUE of int is 2^31-1, so (endBit - startBit + 1) must
		// <=31

		int counterNum = 1 << (endBit - startBit + 1);
		int[] counter = new int[counterNum];

		long L = (long) Math.pow(2, endBit + 1) - 1;
		L = L >> startBit;
		L = L << startBit;

		// calculate count
		for (int i = 0; i < array.length; i++)
		{
			long value = array[i];
			value = value & L;
			value = value >> startBit;

			counter[(int) value]++;
		}

		// merge count
		for (int i = 1; i < counter.length; i++)
		{
			counter[i] = counter[i - 1] + counter[i];
		}

		// sort array according to count
		for (int i = array.length - 1; i >= 0; i--)
		{
			long value = array[i];
			value = value & L;
			value = value >> startBit;

			result[counter[(int) value] - 1] = array[i];
			counter[(int) value]--;
		}

		// copy back
		return result;
	}

	public static void main(String args[])
	{
		int num = 100000000;

		Random rand = new Random();
		long[] array = new long[num];
		for (int i = 0; i < num; i++)
		{
			array[i] = rand.nextInt(Integer.MAX_VALUE);
		}

		long start = System.currentTimeMillis();

		SortingAlgorithm4Long sortor = new SortingAlgorithm4Long();
		// // sortor.insertionSort(array);
		sortor.quickSort(array, 0, array.length - 1);
		// sortor.mergeSort(array, 0, array.length - 1);
		// // array = sortor.countingSort(array, 5, 10);
		// array = sortor.radixSort(array, 8);

		// for (int i = 0; i < 10; i++)
		// {
		// System.out.print(array[i] + " ");
		// }
		// System.out.println();

		long end = System.currentTimeMillis();
		System.out.println("Time : " + (end - start) + "(ms)");
		System.out.println("Minimum : " + array[0]);
		System.out.println("Maximum : " + array[num - 1]);
	}
}
